<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            目标和 II：
            输入：nums = [1,1,1,1,1], target = 3
            输出：5
            解释：一共有 5 种方法让最终目标和为 3 。
            -1 + 1 + 1 + 1 + 1 = 3
            +1 - 1 + 1 + 1 + 1 = 3
            +1 + 1 - 1 + 1 + 1 = 3
            +1 + 1 + 1 - 1 + 1 = 3
            +1 + 1 + 1 + 1 - 1 = 3

            题目描述：
            1. 所有数组前面添加上+和-，构造成表达式
            2. 在给他们求和
            3. 结果要等于目标和
            4. 表达式的种类的数目

            判断是01背包：
            这题关键是如何把“+和-的表达式的和”转化为“01背包问题”
            0. 把+的表达式的和称为left,把给-的对应数字的和称为right，
                left+right=sum（这是所有数字和）
                left-right=target(这是题目要求的target)
                上面两个表达式，左右都相加，就是2left=sum+target;left = (sum + target) / 2
                题目此时转化为，求取和为(sum + target)的背包问题


            五部曲：
            1. dp[i][j]的含义：i是数字的下标，j是数字的值，dp[i][j]是从第0-i拿的物品装满j背包后的容量
            2. 确定递推公式：dp[j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
            3. 初始化dp二维数组，第一个数初始化为1，如果值是0初始化为2；
            4. 确定遍历顺序，和01背包一样，先遍历数字，再遍历背包的重量就是数字的大小
            5. 递推一下：[1, 1, 1, 1, 1] target为3，输出应该为5

        */
        var findTargetSumWays = function(nums, target) {
            let sum = 0   // 总和
            nums.forEach(num => sum += num)
            // 若sum+target不是非零偶数，表示无法找到对应的left值(+的序列组合)，无方案
            if ((sum + target) % 2 !== 0) return 0
            // target的绝对值大于sum, 无方案
            if (Math.abs(target) > sum) return 0
            let left = (sum + target)  / 2
            // 初始化数组
            // let dp = Array.from({length: nums.length + 1}, (item, index) => new Array(left + 1).fill(0))
            let n = nums.length
            // 一维是n nums的长度，因为从0到n-1都会用到，n - 1也是一个物品，不需要n
            // 二维是 left+1，需要取到left的重量
            let dp = new Array(n).fill(0).map(() => new Array(left + 1).fill(0));
            // 第一个物品如果比left小，初始化第一个物品对应的列
            if (nums[0] <= left) dp[0][nums[0]] = 1
            // 第[0][0]个如果是0，+或者-都可以，第一个应该初始为2,否则为1
            if (nums[0] === 0) dp[0][0] = 2
            else dp[0][0] = 1
            // i要比n小，取到n-1个物品，
            for (let i = 1; i < n; i++) {
                // j要取到left，重量需要为left
                for (let j = 0; j <= left; j++) {
                    // 超重,也是为了初始化第一列
                    if (nums[i] > j) dp[i][j] = dp[i - 1][j]
                    // 这里不是取最大值，而是求和
                    else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
                }
            }
            console.log(dp, 'dp');

            return dp[n - 1][left]
        };
        console.log(findTargetSumWays([1,1,1,1,1], 3));
        // console.log(findTargetSumWays([1], 1));
        // console.log(findTargetSumWays([0,0,0,0,0,0,0,0,1], 1));
    </script>
</body>

</html>